//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::Pair&
csHashMap<K,V>::iterator::operator *()
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index];
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::Pair*
csHashMap<K,V>::iterator::operator->()
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return &m_pairs[m_index];
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator&
csHashMap<K,V>::iterator::operator ++()
{
	++m_index;
	return *this;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator
csHashMap<K,V>::iterator::operator ++(s32)
{
	return iterator(m_pairs,m_index++);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator&
csHashMap<K,V>::iterator::operator --()
{
	--m_index;
	return *this;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator
csHashMap<K,V>::iterator::operator --(s32)
{
	return iterator(m_pairs,m_index--);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::iterator::operator==(const typename csHashMap<K,V>::iterator& rhs) const
{
	return &m_pairs==&rhs.m_pairs&&m_index==rhs.m_index;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::iterator::operator !=(const typename csHashMap<K,V>::iterator& rhs) const
{
	return !((*this)==rhs);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE
csHashMap<K,V>::iterator::operator bool() const
{
	return m_index>=0&&m_index<m_pairs.size();
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const K&
csHashMap<K,V>::iterator::key() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index].m_key;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE V&
csHashMap<K,V>::iterator::value()
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index].m_value;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const typename csHashMap<K,V>::Pair&
csHashMap<K,V>::const_iterator::operator *() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index];
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const typename csHashMap<K,V>::Pair*
csHashMap<K,V>::const_iterator::operator ->() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return &m_pairs[m_index];
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_iterator&
csHashMap<K,V>::const_iterator::operator++()
{
	++m_index;
	return *this;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_iterator
csHashMap<K,V>::const_iterator::operator ++(s32)
{
	return const_iterator(m_pairs,m_index++);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_iterator&
csHashMap<K,V>::const_iterator::operator --()
{
	--m_index;
	return *this;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_iterator
csHashMap<K,V>::const_iterator::operator --(s32)
{
	return const_iterator(m_pairs,m_index--);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::const_iterator::operator ==(const typename csHashMap<K,V>::const_iterator &rhs) const
{
	return &m_pairs==&rhs.m_pairs&&m_index==rhs.m_index;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::const_iterator::operator !=(const typename csHashMap<K,V>::const_iterator& rhs) const
{
	return !((*this)==rhs);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE 
csHashMap<K,V>::const_iterator::operator bool() const
{
	return m_index>=0&&m_index<m_pairs.size();
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const K&
csHashMap<K,V>::const_iterator::key() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index].m_key;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const V&
csHashMap<K,V>::const_iterator::value() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index].m_value;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::Pair&
csHashMap<K,V>::reverse_iterator::operator *()
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index];
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::Pair*
csHashMap<K,V>::reverse_iterator::operator ->()
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return &m_pairs[m_index];
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::reverse_iterator&
csHashMap<K,V>::reverse_iterator::operator ++()
{
	--m_index;
	return *this;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::reverse_iterator
csHashMap<K,V>::reverse_iterator::operator ++(s32)
{
	return reverse_iterator(m_pairs,m_index--);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::reverse_iterator&
csHashMap<K,V>::reverse_iterator::operator --()
{
	++m_index;
	return *this;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::reverse_iterator
csHashMap<K,V>::reverse_iterator::operator --(s32)
{
	return reverse_iterator(m_pairs,m_index++);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::reverse_iterator::operator==(const typename csHashMap<K,V>::reverse_iterator& rhs) const
{
	return &m_pairs==&rhs.m_pairs&&m_index==rhs.m_index;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::reverse_iterator::operator !=(const typename csHashMap<K,V>::reverse_iterator &rhs) const
{
	return !((*this)==rhs);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE
csHashMap<K,V>::reverse_iterator::operator bool() const
{
	return m_index>=0&&m_index<m_pairs.size();
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const K&
csHashMap<K,V>::reverse_iterator::key() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index].m_key;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE V&
csHashMap<K,V>::reverse_iterator::value()
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index].m_value;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const typename csHashMap<K,V>::Pair&
csHashMap<K,V>::const_reverse_iterator::operator *() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index];
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const typename csHashMap<K,V>::Pair*
csHashMap<K,V>::const_reverse_iterator::operator ->() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return &m_pairs[m_index];
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_reverse_iterator&
csHashMap<K,V>::const_reverse_iterator::operator ++()
{
	--m_index;
	return *this;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_reverse_iterator
csHashMap<K,V>::const_reverse_iterator::operator ++(s32)
{
	return const_reverse_iterator(m_pairs,m_index--);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_reverse_iterator&
csHashMap<K,V>::const_reverse_iterator::operator --()
{
	++m_index;
	return *this;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_reverse_iterator
csHashMap<K,V>::const_reverse_iterator::operator --(s32)
{
	return const_reverse_iterator(m_pairs,m_index++);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::const_reverse_iterator::operator ==(const typename csHashMap<K,V>::const_reverse_iterator &rhs) const
{
	return m_index==rhs.m_index&&&m_pairs==&rhs.m_pairs;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::const_reverse_iterator::operator !=(const typename csHashMap<K,V>::const_reverse_iterator& rhs) const
{
	return !((*this)==rhs);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE
csHashMap<K,V>::const_reverse_iterator::operator bool() const
{
	return m_index>=0&&m_index<m_pairs.size();
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const K&
csHashMap<K,V>::const_reverse_iterator::key() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index].m_key;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const V&
csHashMap<K,V>::const_reverse_iterator::value() const
{
	csASSERT(m_index>=0&&m_index<m_pairs.size());
	return m_pairs[m_index].m_value;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE
csHashMap<K,V>::csHashMap()
:m_hashCount(8)
,m_hash(csNULL)
{
	m_hash = csNEW s32[m_hashCount];
	for(s32 i=0;i<m_hashCount;i++)
	{
		m_hash[i] = csHASH_INDEX_NONE;
	}
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE
csHashMap<K,V>::csHashMap(s32 capacity)
:m_hashCount(8)
,m_hash(csNULL)
,m_pairs(capacity)
{
	m_hash = csNEW s32[m_hashCount];
	for(s32 i=0;i<m_hashCount;i++)
	{
		m_hash[i] = csHASH_INDEX_NONE;
	}
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE
csHashMap<K,V>::csHashMap(const csHashMap<K,V> &hash)
:m_hashCount(hash.m_hashCount)
,m_hash(csNULL)
,m_pairs(hash.m_pairs)
{
	_rehash();
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE
csHashMap<K,V>::~csHashMap()
{
	csSAFE_DELETE_ARRAY(m_hash);
	m_hashCount = 8;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator
csHashMap<K,V>::begin()
{
	return iterator(m_pairs,0);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_iterator
csHashMap<K,V>::begin() const
{
	return const_iterator(m_pairs,0);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator
csHashMap<K,V>::end()
{
	return iterator(m_pairs,m_pairs.size());
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_iterator
csHashMap<K,V>::end() const
{
	return const_iterator(m_pairs,m_pairs.size());
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::reverse_iterator
csHashMap<K,V>::rbegin()
{
	return reverse_iterator(m_pairs,m_pairs.size()-1);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_reverse_iterator
csHashMap<K,V>::rbegin() const
{
	return const_reverse_iterator(m_pairs,m_pairs.size()-1);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::reverse_iterator
csHashMap<K,V>::rend()
{
	return reverse_iterator(m_pairs,-1);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_reverse_iterator
csHashMap<K,V>::rend() const
{
	return const_reverse_iterator(m_pairs,-1);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE void
csHashMap<K,V>::clear()
{
	m_pairs.clear();
	for(s32 i=0;i<m_hashCount;i++)
	{
		m_hash[i] = csHASH_INDEX_NONE;
	}
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE s32
csHashMap<K,V>::count(const K& k) const
{
	return csHASH_INDEX_NONE==_findIndex(k)?0:1;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::hasKey(const K& k) const
{
	return csHASH_INDEX_NONE==_findIndex(k)?false:true;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE bool
csHashMap<K,V>::empty() const
{
	return m_pairs.empty();
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE void
csHashMap<K,V>::set(const K& k, const V& v)
{
	s32 idx = _findIndex(k);
	if(csHASH_INDEX_NONE==idx)
	{
		_add(k,v);
	}
	else
	{
		m_pairs[idx].m_value = v;
	}
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE V&
csHashMap<K,V>::operator [](const K& k)
{
	s32 idx = _findIndex(k);
	if(csHASH_INDEX_NONE==idx)
	{
		_add(k,V());
		return m_pairs.back().m_value;
	}
	return m_pairs[idx].m_value;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const V&
csHashMap<K,V>::operator [](const K& k) const
{
	s32 idx = _findIndex(k);
	if(csHASH_INDEX_NONE==idx)
	{
		(const_cast<csHashMap<K,V>* >(this))->_add(k,V());
		return m_pairs.back().m_value;
	}
	return m_pairs[idx].m_value;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE V*
csHashMap<K,V>::findValue(const K& k)
{
	s32 idx = _findIndex(k);
	return csHASH_INDEX_NONE==idx?csNULL:&m_pairs[idx].m_value;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE const V*
csHashMap<K,V>::findValue(const K& k) const
{
	s32 idx = _findIndex(k);
	return csHASH_INDEX_NONE==idx?csNULL:&m_pairs[idx].m_value;
}

//------------------------------------------------------------------------
template<typename K,typename V> const K*
csHashMap<K,V>::findKey(const V& v, const K* fromKey) const
{
	s32 beginIdx = 0;
	if(csNULL!=fromKey)
	{
		s32 idx		= _findIndex(*fromKey);
		beginIdx	= csHASH_INDEX_NONE!=idx?idx:0;
	}
	for(s32 i=beginIdx;i<m_pairs.size();i++)
	{
		if(m_pairs[i].m_value==v)
		{
			return &m_pairs[i].m_key;
		}
	}
	return csNULL;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE void
csHashMap<K,V>::remove(const K& k)
{
	s32 idx = _findIndex(k);
	if(csHASH_INDEX_NONE!=idx)
	{
		m_pairs.erase(idx);
		_relax();
	}
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator
csHashMap<K,V>::erase(typename csHashMap<K,V>::iterator where)
{
	csASSERT(&where.m_pairs==&m_pairs);
	csASSERT(where);
	m_pairs.erase(where.m_index);
	_relax();
	return where;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator
csHashMap<K,V>::erase(typename csHashMap<K,V>::iterator from, typename csHashMap<K,V>::iterator to)
{
	csASSERT(&from.m_pairs==&to.m_pairs&&&from.m_pairs==&m_pairs);
	csASSERT(from&&(to.m_index>=0&&to.m_index<=m_pairs.size()));
	m_pairs.erase(from.m_index,to.m_index-from.m_index);
	_relax();
	return from;
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::iterator
csHashMap<K,V>::find(const K& k)
{
	s32 idx = _findIndex(k);
	if(csHASH_INDEX_NONE==idx)
	{
		return end();
	}
	return iterator(m_pairs,idx);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE typename csHashMap<K,V>::const_iterator
csHashMap<K,V>::find(const K& k) const
{
	s32 idx = _findIndex(k);
	if(csHASH_INDEX_NONE==idx)
	{
		return end();
	}
	return const_iterator(m_pairs,idx);
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE s32
csHashMap<K,V>::size() const
{
	return m_pairs.size();
}

//------------------------------------------------------------------------
template<typename K,typename V> csINLINE void
csHashMap<K,V>::swap(csHashMap<K,V>& rhs)
{
	m_pairs.swap(rhs.m_pairs);
	csSwap<s32>(m_hashCount,rhs.m_hashCount);
	csSwap<s32*>(m_hash,rhs.m_hash);
}

//------------------------------------------------------------------------
template<typename K,typename V> s32
csHashMap<K,V>::_findIndex(const K& k) const
{
	if(m_hash&&m_pairs.size()>0)
	{
		for(s32 i=m_hash[GetTypeHash(k)&(m_hashCount-1)];i!=csHASH_INDEX_NONE;i=m_pairs[i].m_hashNext)
		{
			if(k==m_pairs[i].m_key)
			{
				return i;
			}
		}
	}
	return csHASH_INDEX_NONE;
}

//------------------------------------------------------------------------
template<typename K,typename V> void
csHashMap<K,V>::_rehash()
{
	csDELETE[] m_hash;
	m_hash = csNEW s32[m_hashCount];
	for( s32 i=0; i<m_hashCount; i++ )
	{
		m_hash[i] = csHASH_INDEX_NONE;
	}
	for( s32 i=0; i<m_pairs.size(); i++ )
	{
		Pair&	p		= m_pairs[i];
		s32     iHash   = (GetTypeHash(p.m_key) & (m_hashCount-1));
		p.m_hashNext	= m_hash[iHash];
		m_hash[iHash]	= i;
	}
}

//------------------------------------------------------------------------
template<typename K, typename V> csINLINE void
csHashMap<K,V>::_add(const K& k, const V& v)
{
	m_pairs.push_back(Pair(k,v));
	Pair& p		= m_pairs.back();
	s32 iHash	= (GetTypeHash(k))&(m_hashCount-1);
	p.m_hashNext= m_hash[iHash];
	m_hash[iHash] = m_pairs.size()-1;
	if(m_hashCount*csHASH_REHASH_FACTOR+8<m_pairs.size())
	{
		m_hashCount *= 2;
		_rehash();
	}
}

//------------------------------------------------------------------------
template<typename K, typename V> csINLINE void
csHashMap<K,V>::_relax()
{
	while( m_hashCount>m_pairs.size()*csHASH_REHASH_FACTOR+8 )
	{
		m_hashCount /= 2;
	}
	_rehash();
}